package leetcode;

import java.util.ArrayList;
import java.util.List;

public class PascalTriangle {
	
	public static void main(String[] args) {
		System.out.println(getRow(4));
	}
	
	public ArrayList<ArrayList<Integer>> generate(int numRows) {
        ArrayList<ArrayList<Integer>> lists = new ArrayList<ArrayList<Integer>>();
        ArrayList<Integer> list = new ArrayList<Integer>();
        if(numRows == 0){
            return lists;
        }
        list.add(1);
        lists.add(new ArrayList<Integer>(list));
        for(int i = 1; i < numRows; i++){
            list.clear();
            list.add(1); 
            for(int j = 1; j < i; j++){
                list.add(lists.get(i - 1).get(j - 1) + lists.get(i - 1).get(j));
            }
            list.add(1);
            lists.add(new ArrayList<Integer>(list));
        }
        return lists;
    }
	
	public List<List<Integer>> generate2(int numRows) {
		List<List<Integer>> res = new ArrayList<List<Integer>>();
		if (numRows <= 0) {
			return res;
		}
		List<Integer> list = new ArrayList<>();
		List<Integer> temp = new ArrayList<>();
		temp.add(1);
		res.add(temp);
		if (numRows == 1) {
			return res;
		}
		int length = 0;
		for (int i = 1; i < numRows; i++) {
			length = temp.size();
			list.add(1);
			for (int j = 1; j < length; j++) {
				list.add(temp.get(j - 1) + temp.get(j));
			}
			list.add(1);
			res.add(new ArrayList<>(list));
			temp = new ArrayList<>(list);
			list.clear();
		}
		return res;
	}
	
	//return the kth
	//Given an index k, return the kth row of the Pascal's triangle.
	//For example, given k = 3, Return[1,3,3,1].
	//Space O(n);
	
	public static ArrayList<Integer> getRow(int rowIndex) {
		ArrayList<Integer> list = new ArrayList<Integer>();
		if (rowIndex < 0) {
			return list;
		}
		for (int i = 0; i <= rowIndex; i++) {
			list.add(0, 1); //注意这里添加了一个元素，导致所有的元素都往后移了
			for (int j = 1; j < i; j++) {
				System.out.println(i + "层 " + j + "个" + list.get(j) + "  " + list.get(j + 1));
				//添加了一个元素就是 j + 1 与j 而不是 j 和 j - 1的原因
				list.set(j, list.get(j + 1) + list.get(j));
			}
			list.set(i, 1);
		}
		return list;
	}
}
